`
https://leetcode.cn/problems/largest-rectangle-in-histogram/
`

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
  // 单调栈解法
  // 我们需要求出每个元素的下一个最小元素
  const st = []
  let res = 0
  // 最后加个 0，处理最后留在栈里的部分
  heights.push(0)
  for (let r = 0; r < heights.length; r++) {
    // 所以要保持单调递减，即每次入栈只能比栈顶更大
    // 遇到更小的将要入栈的元素，便可以更新一次结果
    while (st.length && heights[r] <= heights[st[st.length - 1]]) {
      // 取出栈顶
      const i = st.pop()
      // 计算左边的最小位置
      const l = st.length ? st[st.length - 1] : -1
      // 更新结果
      res = Math.max(res, (r - l - 1) * heights[i])
    }
    // 遇到比将入栈元素更小的元素的时候便可以将当前元素入栈了
    st.push(r)
  }

  return res
};